<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>哈希表</title>
</head>
<body>
<script>
    // 创建HashTable构造函数
    function HashTable() {
        // 定义属性
        this.storage = []
        this.count = 0
        this.limit = 8

        // 定义相关方法
        // 判断是否是质数
        HashTable.prototype.isPrime = function (num) {
            var temp = parseInt(Math.sqrt(num))
            // 2.循环判断
            for (var i = 2; i <= temp; i++) {
                if (num % i == 0) {
                    return false
                }
            }
            return true
        }

        // 获取质数
        HashTable.prototype.getPrime = function (num) {
            while (!isPrime(num)) {
                num++
            }
            return num
        }

        // 哈希函数
        HashTable.prototype.hashFunc = function(str, max) {
            // 1.初始化hashCode的值
            var hashCode = 0

            // 2.霍纳算法, 来计算hashCode的数值
            for (var i = 0; i < str.length; i++) {
                hashCode = 37 * hashCode + str.charCodeAt(i)
            }

            // 3.取模运算
            hashCode = hashCode % max
            return hashCode
        }

        // 插入数据方法
        HashTable.prototype.put = function (key, value) {
            // 1.获取key对应的index
            var index = this.hashFunc(key, this.limit)

            // 2.取出数组(也可以使用链表)
            // 数组中放置数据的方式: [[ [k,v], [k,v], [k,v] ] , [ [k,v], [k,v] ]  [ [k,v] ] ]
            var bucket = this.storage[index]

            // 3.判断这个数组是否存在
            if (bucket === undefined) {
                // 3.1创建桶
                bucket = []
                this.storage[index] = bucket
            }

            // 4.判断是新增还是修改原来的值.
            var override = false
            for (var i = 0; i < bucket.length; i++) {
                var tuple = bucket[i]
                if (tuple[0] === key) {
                    tuple[1] = value
                    override = true
                }
            }

            // 5.如果是新增, 前一步没有覆盖
            if (!override) {
                bucket.push([key, value])
                this.count++

                if (this.count > this.limit * 0.75) {
                    var primeNum = this.getPrime(this.limit * 2)
                    this.resize(primeNum)
                }
            }
        }

        // 获取存放的数据
        HashTable.prototype.get = function (key) {
            // 1.获取key对应的index
            var index = this.hashFunc(key, this.limit)

            // 2.获取对应的bucket
            var bucket = this.storage[index]

            // 3.如果bucket为null, 那么说明这个位置没有数据
            if (bucket == null) {
                return null
            }

            // 4.有bucket, 判断是否有对应的key
            for (var i = 0; i < bucket.length; i++) {
                var tuple = bucket[i]
                if (tuple[0] === key) {
                    return tuple[1]
                }
            }

            // 5.没有找到, return null
            return null
        }

        // 删除数据
        HashTable.prototype.remove = function (key) {
            // 1.获取key对应的index
            var index = this.hashFunc(key, this.limit)

            // 2.获取对应的bucket
            var bucket = this.storage[index]

            // 3.判断同是否为null, 为null则说明没有对应的数据
            if (bucket == null) {
                return null
            }

            // 4.遍历bucket, 寻找对应的数据
            for (var i = 0; i < bucket.length; i++) {
                var tuple = bucket[i]
                if (tuple[0] === key) {
                    bucket.splice(i, 1)
                    this.count--

                    // 缩小数组的容量
                    if (this.limit > 7 && this.count < this.limit * 0.25) {
                        var primeNum = this.getPrime(Math.floor(this.limit / 2))
                        this.resize(primeNum)
                    }
                }
                return tuple[1]
            }

            // 5.来到该位置, 说明没有对应的数据, 那么返回null
            return null
        }

        // isEmpty方法
        HashTable.prototype.isEmpty = function () {
            return this.count == 0
        }

        // size方法
        HashTable.prototype.size = function () {
            return this.count
        }

        // 哈希表扩容
        HashTable.prototype.resize = function (newLimit) {
            // 1.保存旧的数组内容
            var oldStorage = this.storage

            // 2.重置属性
            this.limit = newLimit
            this.count = 0
            this.storage = []

            // 3.遍历旧数组中的所有数据项, 并且重新插入到哈希表中
            oldStorage.forEach(function (bucket) {
                // 1.bucket为null, 说明这里面没有数据
                if (bucket == null) {
                    return
                }

                // 2.bucket中有数据, 那么将里面的数据重新哈希化插入
                for (var i = 0; i < bucket.length; i++) {
                    var tuple = bucket[i]
                    this.put(tuple[0], tuple[1])
                }
            }).bind(this)
        }
    }

    // 测试哈希表
    // 1.创建哈希表
    var ht = new HashTable()

    // 2.插入数据
    ht.put("abc", "123")
    ht.put("cba", "321")
    ht.put("nba", "521")
    ht.put("mba", "520")

    // 3.获取数据
    alert(ht.get("abc"))
    ht.put("abc", "111")
    alert(ht.get("abc"))

    // 4.删除数据
    alert(ht.remove("abc"))
    alert(ht.get("abc"))

    console.log(ht.storage)
</script>
</body>
</html>